package 简单.双指针;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
 * <p>
 * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
 * <p>
 * 来源：https://leetcode-cn.com/problems/merge-sorted-array/
 */
public class 合并两个有序数组_88 {

    public static void main(String[] args) {
        int[] nums1 = {1, 3, 4, 0, 0, 0};
        int[] nums2 = {2, 5, 6};
        merge(nums1, 3, nums2, 3);
    }

    //双指针，在两个数组首部分别定义一个指针，判断指向的数字哪个更小，更小的指针+1
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        List<Integer> list = new ArrayList<>(m + n);
        int n1 = 0;
        int n2 = 0;
        //当两个数组的下标均超出范围时，退出循环
        while (n1 < m || n2 < n) {
            //当数组1超出范围时，此时数组1中的数字全部处理完成，只需处理数组2
            if (n1 == m) {
                list.add(nums2[n2++]);
            } else if (n2 == n) {
                list.add(nums1[n1++]);
            } else if (nums1[n1] > nums2[n2]) {  //取指针较小的数字
                list.add(nums2[n2++]);
            } else {
                list.add(nums1[n1++]);
            }
        }
        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = list.get(i);
        }
    }

}
